package com.heima.leetcode.practice;

import java.util.*;

/**
 * @description: leetcode 169. 多数元素
 * @author 勾新杰
 * @version 1.0
 * @date 2025/1/22 13:01
 */
public class E169 {

    private final HashMap<Integer,Integer> map = new HashMap<>();

    /**
     * <h3>方法一：用哈希表和stream流</h3>
     * @param nums nums数组
     * @return 多数元素
     */
    public int majorityElement1(int[] nums) {
        for (int num : nums)
            map.compute(num, (k, v) -> v == null ? 1 : v + 1);
        return map.entrySet().stream()
                .max(Comparator.comparingInt(Map.Entry::getValue))
                .map(Map.Entry::getKey)
                .orElseThrow(NoSuchElementException::new);
    }

    /**
     * <h3>方法二：用哈希表</h3>
     * @param nums nums数组
     * @return 多数元素
     */
    public int majorityElement2(int[] nums) {
        for (int num : nums) {
            if (map.containsKey(num))
                map.put(num, map.get(num) + 1);
            else map.put(num, 1);
        }
        for (Map.Entry<Integer, Integer> entry : map.entrySet())
            if (entry.getValue() > nums.length >> 1)
                return entry.getKey();
        return -1;
    }

    /**
     * <h3>方法三：排序法</h3>
     * @param nums nums数组
     * @return 多数元素
     */
    public int majorityElement3(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length >> 1];
    }

    /**
     * <h3>方法四：摩尔投票法，时间复杂度O(N)，空间复杂度：O(1)，思想：抵消</h3>
     * <p>投票算法只针对于多数问题有用，也就是多余一半以上的数能用，而对于一般的众数不行</p>
     * @param nums nums数组
     * @return 多数元素
     */
    public int majorityElement4(int[] nums) {
        int count = 1, candidate = nums[0];
        for (int i = 1; i < nums.length; i++){
            if (count == 0) candidate = nums[i];
            if (nums[i] == candidate) count++;
            else count--;
        }
        return candidate;
    }
}
